murrax.dev Recently Edited: Learning with ObsidianObject Capabilities Security ModelGPU Architecture

Quadratic Arithmetic Programs

A [[Rank 1 Constraint System]] (R1CS) represented as a set of polynomials instead of matrices and vectors. The motivation is to be able to perform quicker equality testing.

Derivation from R1CS

We can represent vectors as polynomials by treating the elements in the vector as $y$ values on a polynomial, e.g. a vector $[4,9,16]$ would become simply $x^2$ assuming we have a base $x$ vector of $[2,3,4]$ . We can obtain this polynomial using Lagrange interpolation.

Vector addition is homomorphic to polynomial addition, i.e. $L(v+w) = L(v) + L(w)$

Matrix-vector multiplication as vector-scalar multiplication

A\cdot v = \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14}\\ a_{21} & a_{22} & a_{23} & a_{24}\\ a_{31} & a_{32} & a_{33} & a_{34}\\ \end{bmatrix} \cdot \begin{bmatrix} v_1\\ v_2\\ v_3\\ v_4\\ \end{bmatrix}

can be rewritten as

A\cdot v = \begin{bmatrix} a_{11}\\ a_{21}\\ a_{31}\\ \end{bmatrix} \cdot v_1, \begin{bmatrix} a_{12}\\ a_{22}\\ a_{32}\\ \end{bmatrix} \cdot v_2, \begin{bmatrix} a_{13}\\ a_{23}\\ a_{33}\\ \end{bmatrix} \cdot v_3, \begin{bmatrix} a_{14}\\ a_{24}\\ a_{34}\\ \end{bmatrix} \cdot v_4

Now we can represent these vectors as polynomials.

Equality testing

Over a large enough field, the intersections of these polynomials is negligible as given by the Schwartz-Zippel Lemma, meaning by simply comparing the $y$ values at the same $x$ position on both polynomials, we can check for equality of the vectors. This is in $O(1)$ time, instead of $O(n)$ where $n$ is the size of the vector. This is of course excluding the overhead of converting into a polynomial, and calculating the polynomial value. In fact the important saving here isn’t in the time, but in the space, as this way we only need to transfer and prove one field element instead of $n$ .

Once we have $Oa = La \cdot Ra$ in polynomial forms, we can simply multiply through by the scalars, and then sum the resulting polynomials for $Oa, La, Ra$ to get $w(x) = u(x)\cdot v(x)$ .

However, we cannot simply multiply $u(x)v(x)$ as this would result in a polynomial of higher degree than $w(x)$ . We must also add a compensating polynomial $b(x)=u(x)v(x)-w(x)$ with roots at the $x$ values we are using for our interpolation to $w(x)$ , which brings them to the same degree, while leaving the interpolation intact.

In order to prevent the prover from choosing a malicious $b(x)$ which does not have the correct roots, we must limit its form. We do this by decomposing it into $b(x)=h(x)t(x)$ , where $t(x)=(x-1)(x-2)...(x-n)$ , this means that no matter what $h(x)$ is, it will multiply out with the same roots. We can then compute $h(x)=\frac{u(x)v(x)-w(x)}{t(x)}$

References

https://rareskills.io/post/quadratic-arithmetic-program